/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     Node* next;
 *     Node* random;
 * };
 */

class Solution 
{
public:
    Node* copyRandomList(Node* head) 
    {
        if (head == nullptr)
            return nullptr; // 处理空链表情况

        Node* cur = head; // 1. 在每个原节点后面插入复制节点
        while (cur != nullptr) 
        {
            Node* copy = new Node(cur->val); // 创建新节点
            copy->next = cur->next; // 插入新节点
            cur->next = copy;
            cur = copy->next; // 移动到下一个原节点
        }

        cur = head; // 2. 处理复制节点的random指针
        while (cur != nullptr) 
        {
            Node* copy = cur->next;
            if (cur->random == nullptr) // 原节点random为空的情况
                copy->random = nullptr;
            else // 复制random指针
                copy->random = cur->random->next;
            cur = copy->next; // 移动到下一个原节点
        }

        Node* copy_head = nullptr; // 3. 分离原链表和复制链表
        Node* copy_tail = nullptr;
        cur = head;
        while (cur != nullptr) 
        {
            Node* copy = cur->next;
            Node* next = copy->next;
            if (copy_head == nullptr) // 初始化复制链表的头尾指针
            {
                copy_head = copy_tail = copy;
            }
            else // 将复制节点连接到复制链表
            {
                copy_tail->next = copy;
                copy_tail = copy;
            }
            cur->next = next; // 恢复原链表的连接
            cur = next; // 移动到下一个原节点
        }
        return copy_head; // 返回复制链表的头节点
    }
};